import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Stack;

/*
 * @lc app=leetcode.cn id=456 lang=java
 *
 * [456] 132模式
 */

// @lc code=start
class Solution {
    //有点像模拟，怎么说呢
    //单调栈方法，好难理解啊。
    public boolean find132pattern(int[] nums) {
        if(nums.length<3) return false;
        Stack<Integer> st = new Stack<>();
        int len = nums.length;
        int last = Integer.MIN_VALUE;//记录132中的2。
        //从后往前扫
        for(int i = len-1;i>=0 ;i--){
            if(nums[i]<last) return true;//如果1<2，且中间必有个3

            // 若当前值大于或等于2则更新2（2为栈中小于当前值的最大元素）
            // 注意这个栈一定是个单调递增的栈，栈顶元素一定是最小的
            // 因为如果某个元素比栈顶元素大，那么栈顶元素就会被弹出。
            // 所以到最后，栈内元素一定是从栈顶到栈底递增的。
            while(!st.isEmpty() && nums[i]>st.peek()){
                last = st.pop();
            }
            // 当前值入栈
            st.push(nums[i]);
        }
        return false;
        
    }
    
}
// @lc code=end

